/**
 * @file 简单题大杂烩
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-12
 * 
 * @copyright Copyright (c) 2021
 * 
 * 03.数组中重复的数字
 * 09.用两个栈实现队列
 * 30.包含min函数的栈 -- O(1)时间获取栈中最小元素
 * **/
#include <iostream>
#include <stack>
#include <vector>
using namespace std;

void printVec(vector<int> &nums)
{
    for (auto &num : nums) {
        cout << num << " ";
    }
    cout << endl;
}
class Solution
{
public:
    // 03.数组中重复的数字
    int findRepeatNumber(vector<int> &nums)
    {
        vector<int> hash(nums.size(), 0);
        for (auto &num : nums) {
            hash[num] += 1;
            if (hash[num] == 2) {
                return num;
            }
        }
        return nums[0];
    }
};
// 09.
class CQueue
{
public:
    void appendTail(int value)
    {
        stk1.push(value);
    }

    int deleteHead()
    {
        while (1) {
            if (!stk2.empty()) {
                int val = stk2.top();
                stk2.pop();
                return val;
            } else if (stk1.empty()) {
                return -1;
            } else {
                while (!stk1.empty()) {
                    stk2.push(stk1.top());
                    stk1.pop();
                }
            }
        }
    }

private:
    stack<int> stk1; // 栈序，入队用
    stack<int> stk2; // 存队列序，弹队头用
};
// 30.
class MinStack
{
public:
    void push(int x)
    {
        stk1.push(x);
        if (stk2.empty() || stk2.top() >= x) {
            stk2.push(x);
        }
    }

    void pop()
    {
        if (stk1.top() == stk2.top()) {
            stk2.pop();
        }
        stk1.pop();
    }

    int top()
    {
        return stk1.top();
    }

    int min()
    {
        return stk2.top();
    }

private:
    stack<int> stk1;
    stack<int> stk2; // 单调不增栈，栈顶即minstack
};

int main()
{
    Solution solve = Solution();
    // vector<int> nums = {2, 3, 1, 0, 2, 5, 3};
    // cout << solve.findRepeatNumber(nums) << endl;
}